ট্রি (Trees)

ট্রি হল একটি বিশেষ ধরনের গ্রাফ যা গাণিতিক ও কম্পিউটার বিজ্ঞানে কাঠামোগত ডেটা মডেল করতে ব্যবহৃত হয়। এটি একটি সংযুক্ত ও চক্রবিহীন গ্রাফ (Acyclic Graph), যা একটি হায়ারারকিকাল স্ট্রাকচার বা স্তরবিন্যাস কাঠামো গঠন করে। ট্রির মাধ্যমে বিভিন্ন ডেটা, যেমন ফাইল সিস্টেম, ডাটাবেস ইন্ডেক্সিং, এবং প্রোগ্রামিং কাঠামো সংগঠিত করা হয়।

ট্রির মৌলিক ধারণা (Basic Concepts of Trees)

রুট নোড (Root Node): ট্রির শুরু বিন্দু বা শীর্ষ নোড। এটি ট্রির প্রথম স্তর এবং এর পূর্বে আর কোন নোড নেই।

চাইল্ড নোড (Child Node): একটি নোডের অধীনস্ত নোডকে চাইল্ড নোড বলা হয়। চাইল্ড নোডগুলো তাদের অভিভাবক নোড বা প্যারেন্ট নোডের সাথে সংযুক্ত থাকে।

প্যারেন্ট নোড (Parent Node): যে নোডের অধীনে অন্যান্য চাইল্ড নোড রয়েছে তাকে প্যারেন্ট নোড বলা হয়।

লিফ নোড (Leaf Node): যে নোডের আর কোন চাইল্ড নোড নেই তাকে লিফ নোড বলা হয়। এটি ট্রির শেষ স্তরের নোড।

সাবট্রি (Subtree): একটি নোড এবং তার অধীনস্ত সকল নোড সমন্বয়ে গঠিত একটি ক্ষুদ্র ট্রি, যা পুরো ট্রির অংশ।

ট্রির বৈশিষ্ট্য (Properties of Trees)

সংযুক্তি (Connected): ট্রির প্রতিটি নোড একটি সংযুক্ত কাঠামোতে থাকে, অর্থাৎ প্রতিটি নোডে রুট থেকে একটি পথ রয়েছে।

চক্রবিহীন (Acyclic): ট্রিতে কোন চক্র বা সাইকেল থাকে না। এটি নিশ্চিত করে যে ট্রিতে কোন নোড একাধিকবার পরিদর্শন করা হবে না।

এজের সংখ্যা: nnn সংখ্যক নোডের জন্য ট্রিতে সর্বদা n−1n - 1n−1 এজ থাকে।

লেভেল (Level): রুট থেকে একটি নির্দিষ্ট দূরত্বে থাকা নোডগুলোকে একটি নির্দিষ্ট স্তরে (level) রাখা হয়। রুট নোডের স্তর 0, তার চাইল্ড নোডগুলোর স্তর 1, এবং এভাবে ক্রমাগত স্তর বাড়তে থাকে।

ট্রির প্রকারভেদ (Types of Trees)

বাইনারি ট্রি (Binary Tree): প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড থাকে। এটি গাণিতিক অপারেশন, সার্চিং ও ইন্ডেক্সিংয়ে ব্যবহৃত হয়।

বাইনারি সার্চ ট্রি (Binary Search Tree): একটি বিশেষ বাইনারি ট্রি যেখানে বাম দিকের চাইল্ড নোড ছোট এবং ডান দিকের চাইল্ড নোড বড় মান ধারণ করে। এটি দ্রুত ডেটা সার্চ ও ইন্সার্ট করতে সহায়ক।

ব্যালেন্সড ট্রি (Balanced Tree): প্রতিটি স্তরে নোডগুলি সুষমভাবে বিভক্ত থাকে, যা ট্রির উচ্চতা সীমিত রাখে এবং সার্চ অপারেশন দ্রুত হয়।

এভিএল ট্রি (AVL Tree): একটি স্বয়ং-সুষমিত বাইনারি সার্চ ট্রি, যেখানে প্রতিটি নোডের বাম ও ডান সাবট্রির উচ্চতা পার্থক্য সর্বাধিক ১ থাকে।

হিপ ট্রি (Heap Tree): একটি সম্পূর্ণ বাইনারি ট্রি যা সর্বোচ্চ (ম্যাক্স হিপ) বা সর্বনিম্ন (মিন হিপ) মানের উপর ভিত্তি করে সাজানো হয়।

ট্রির প্রয়োগ (Applications of Trees)

ফাইল সিস্টেম: কম্পিউটারের ফাইল সিস্টেমে ফোল্ডার এবং সাবফোল্ডারগুলিকে হায়ারারকিকাল কাঠামোতে সংগঠিত করতে ট্রি ব্যবহার করা হয়।

ডেটাবেস ইন্ডেক্সিং: দ্রুত ডেটা রিট্রিভ করতে B-Tree এবং B+ Tree ইন্ডেক্সিং ব্যবহৃত হয়।

নেটওয়ার্ক রাউটিং: ট্রি স্ট্রাকচার নেটওয়ার্ক রাউটিংয়ে ডেটা পথ নির্ধারণে সহায়ক।

এক্সপ্রেশন পার্সিং: গাণিতিক এক্সপ্রেশন এবং কম্পাইলারের সিনট্যাক্স এনালাইসিসে বাইনারি এক্সপ্রেশন ট্রি ব্যবহৃত হয়।

কৃত্রিম বুদ্ধিমত্তা: ডিসিশন ট্রি মেশিন লার্নিং এবং কৃত্রিম বুদ্ধিমত্তায় সিদ্ধান্ত গ্রহণ প্রক্রিয়ার মডেলিংয়ে ব্যবহৃত হয়।

সারসংক্ষেপ (Summary)

ট্রি হল একটি গাণিতিক ও সংগঠিত কাঠামো যা বিভিন্ন উপাদানগুলিকে হায়ারারকিকাল স্ট্রাকচারে সাজায়। এটি ডেটা মডেলিং, ফাইল সিস্টেম, ডেটাবেস, নেটওয়ার্কিং, এবং মেশিন লার্নিংয়ের মতো বিভিন্ন ক্ষেত্রে গুরুত্বপূর্ণ ভূমিকা পালন করে। বিভিন্ন ধরনের ট্রি কাঠামো বিভিন্ন প্রয়োজনে ব্যবহার করা হয়, যেমন বাইনারি সার্চ ট্রি, এভিএল ট্রি, এবং হিপ ট্রি।

ট্রি এর ধারণা (Concept of Tree)

ট্রি একটি বিশেষ ধরনের গ্রাফ যা একটি সংযোগযুক্ত এবং চক্রবিহীন (Cycle-Free) কাঠামো নির্দেশ করে। এটি একটি রুটেড স্ট্রাকচার যেখানে একটি নোডকে রুট (Root) ধরা হয়, এবং সেই নোড থেকে অন্যান্য নোডগুলোতে সংযোগ স্থাপিত হয়। ট্রি বিভিন্ন উপাদানের মধ্যে সম্পর্ক ও শ্রেণীবিভাগ বুঝতে সহায়ক।

ট্রি-এর মূল বৈশিষ্ট্যগুলো হলো:

• রুটেড নোড (Root Node): ট্রির প্রথম নোড বা শীর্ষ নোড।
• লিফ নোড (Leaf Node): শেষের নোড যেটির কোনো সন্তান (Child) নেই।
• এজ (Edge): নোডগুলোকে সংযুক্ত করার জন্য ব্যবহৃত লাইন।
• উচ্চতা (Height): রুট থেকে লিফ পর্যন্ত সর্বাধিক দৈর্ঘ্যের পথ।
• সাবট্রি (Subtree): মূল ট্রির অধীনে একটি ছোট অংশের ট্রি।

ট্রি এর প্রকারভেদ

• বাইনারি ট্রি (Binary Tree): প্রতিটি নোডের সর্বাধিক দুটি শিশু নোড থাকতে পারে।
• বাইনারি সার্চ ট্রি (Binary Search Tree): একটি বিশেষ ধরনের বাইনারি ট্রি যেখানে বাম দিকের নোডে ছোট মান এবং ডান দিকের নোডে বড় মান থাকে।
• এভিএল ট্রি (AVL Tree): একটি সুষম বাইনারি সার্চ ট্রি, যেখানে প্রতিটি নোডের উচ্চতার পার্থক্য ১ বা ০ থাকে।
• ব্যালান্সড ট্রি (Balanced Tree): এমন ট্রি যেখানে নোডের উচ্চতার পার্থক্য সংরক্ষিত থাকে।

ট্রি এর প্রয়োজনীয়তা (Importance of Trees)

ট্রি বিভিন্ন ক্ষেত্রে প্রয়োজনীয় এবং বাস্তব জীবনে এর গুরুত্বপূর্ণ ভূমিকা রয়েছে। এটি ডেটা সংগঠন, অনুসন্ধান, এবং অপ্টিমাইজেশন প্রক্রিয়ায় সহায়ক।

১. ডেটা সংগঠন (Data Organization)

ট্রি ব্যবহারের মাধ্যমে বিভিন্ন ডেটাকে শ্রেণীবদ্ধ এবং সংগঠিত করা যায়। যেমন ফাইল সিস্টেম, যেখানে ফোল্ডার ও ফাইলের মধ্যে একটি রুট এবং ব্রাঞ্চ কাঠামো থাকে। ট্রির মাধ্যমে তথ্যকে উপ-উপাদান বা বিভাগের মধ্যে বিভক্ত করা যায়।

২. দ্রুত অনুসন্ধান (Efficient Searching)

বাইনারি সার্চ ট্রির মাধ্যমে বড় ডেটাসেটে দ্রুত অনুসন্ধান করা যায়। যেমন: কোন সংখ্যা বা উপাদান খুঁজে বের করতে সাধারণত বাইনারি সার্চ ট্রি ব্যবহার করা হয়, যা সময় অপচয় না করেই দ্রুত ফলাফল প্রদান করে।

৩. হায়ারার্কিকাল ডেটা স্ট্রাকচার (Hierarchical Data Structure)

ট্রি একটি শ্রেণীবদ্ধ ডেটা স্ট্রাকচার, যা পিতামাতা-সন্তান সম্পর্ক নির্দেশ করে। এটি নোডগুলোর মধ্যে সম্পর্ক স্থাপন করতে সহায়ক, যা ওয়েবসাইট মেনু বা শ্রেণীবিভাগমূলক কাঠামোতে ব্যবহৃত হয়।

৪. নেটওয়ার্ক এবং রাউটিং অ্যালগরিদম (Network and Routing Algorithms)

নেটওয়ার্ক এবং যোগাযোগের ক্ষেত্রে ট্রি একটি গুরুত্বপূর্ণ ভূমিকা পালন করে। রাউটিং অ্যালগরিদমগুলোর জন্য ট্রি-ভিত্তিক কাঠামো ব্যবহার করা হয়, যা যোগাযোগ নেটওয়ার্কে পথ নির্ধারণ করে।

৫. ইন্ডেক্সিং (Indexing)

ডেটাবেসে তথ্য সংগঠন ও ইন্ডেক্সিং করার জন্য ট্রি ব্যবহার করা হয়। বিশেষত, বি-ট্রি (B-tree) এবং বি+ ট্রি ডেটাবেস ইন্ডেক্সিংয়ে ব্যবহৃত হয়, যা ডেটার দ্রুত অ্যাক্সেস সরবরাহ করে।

৬. কৃত্রিম বুদ্ধিমত্তা ও সিদ্ধান্ত গঠন (Artificial Intelligence and Decision Making)

ট্রি বিভিন্ন সিদ্ধান্ত গঠন এবং কৃত্রিম বুদ্ধিমত্তার সমস্যার সমাধানে ব্যবহৃত হয়। উদাহরণস্বরূপ, সিদ্ধান্ত ট্রি (Decision Tree) মেশিন লার্নিংয়ের ক্লাসিফিকেশন ও সিদ্ধান্ত প্রক্রিয়ায় ব্যবহৃত হয়।

সারসংক্ষেপ (Summary)

ট্রি একটি গুরুত্বপূর্ণ গাণিতিক কাঠামো যা বিভিন্ন ক্ষেত্রে ডেটা সংগঠন এবং শ্রেণীবিভাগে ব্যবহৃত হয়। এটি দ্রুত অনুসন্ধান, ইন্ডেক্সিং, নেটওয়ার্কিং এবং কৃত্রিম বুদ্ধিমত্তার মতো ক্ষেত্রে কার্যকর। ট্রির মাধ্যমে তথ্যকে গঠিত ও শ্রেণীবদ্ধ করে জটিল সমস্যাগুলোর কার্যকর সমাধান বের করা যায়। ট্রি ডেটা সংগঠনের পাশাপাশি তথ্যের শ্রেণীবিভাগ এবং নেটওয়ার্ক গঠনে একটি শক্তিশালী মাধ্যম।

বাইনারি ট্রি (Binary Tree)

বাইনারি ট্রি হলো একটি বিশেষ ধরনের গাছের (Tree) ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডের সর্বাধিক দুইটি সন্তান থাকতে পারে। এটি সাধারণত লেফট চাইল্ড এবং রাইট চাইল্ড হিসেবে পরিচিত। বাইনারি ট্রি গঠন এবং পরিচালনা সহজ হওয়ার কারণে অনেক ক্ষেত্রে ব্যবহৃত হয়।

• প্রকারভেদ:
  • সম্পূর্ণ বাইনারি ট্রি (Complete Binary Tree): সব লেভেল পূর্ণ থাকে, তবে শেষ স্তরে নোডগুলো বাম থেকে ডানে পূর্ণ না হলেও শেষ স্তরের বাম দিকে নোড থাকবে।
  • পূর্ণ বাইনারি ট্রি (Full Binary Tree): প্রতিটি নোডের বা তো দুইটি সন্তান থাকে, নয়তো কোনো সন্তান থাকে না।
  • পারফেক্ট বাইনারি ট্রি (Perfect Binary Tree): সমস্ত লেভেল পূর্ণ থাকে এবং প্রতিটি স্তরে সমান সংখ্যক নোড থাকে।

BST (Binary Search Tree)

BST বা বাইনারি সার্চ ট্রি একটি বাইনারি ট্রির বিশেষ ধরনের যেখানে প্রতিটি নোডের বাম সন্তান তার চেয়ে ছোট এবং ডান সন্তান তার চেয়ে বড়। এটি একটি কার্যকর উপায়ে ডেটা সংরক্ষণ, অনুসন্ধান এবং সন্নিবেশ (Insertion) এর জন্য ব্যবহৃত হয়।

• বৈশিষ্ট্য:
  • বাম সন্তান (Left Child): সবসময় বর্তমান নোডের চেয়ে ছোট মান ধারণ করে।
  • ডান সন্তান (Right Child): সবসময় বর্তমান নোডের চেয়ে বড় মান ধারণ করে।
• অপারেশন:
  • সন্নিবেশ (Insertion): নতুন মান বাম বা ডান পাশে রাখার জন্য উপযুক্ত অবস্থান খুঁজে নিয়ে স্থাপন করা হয়।
  • অনুসন্ধান (Search): একটি মান খুঁজতে সঠিক পথে চলা হয়, যেমন বড় হলে ডানে যাওয়া এবং ছোট হলে বামে যাওয়া।
  • ডিলিশন (Deletion): একটি নির্দিষ্ট মান মুছে ফেলা হয়, এবং এটি তিনটি অবস্থার উপর ভিত্তি করে হতে পারে—কোনো সন্তান নেই, একটি সন্তান আছে, বা দুইটি সন্তান আছে।

AVL ট্রি (AVL Tree)

AVL ট্রি হলো একটি BST যা ব্যালেন্সড থাকে। এটি একটি সেল্ফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি, যেখানে প্রতিটি নোডের বাম এবং ডান উপ-গাছের উচ্চতার মধ্যে পার্থক্য সর্বাধিক ১ থাকতে পারে। উচ্চতা ভারসাম্য রক্ষা করতে এটিতে রোটেশন অপারেশন রয়েছে।

ব্যালেন্স ফ্যাক্টর: প্রতিটি নোডের বাম উপ-গাছ এবং ডান উপ-গাছের উচ্চতার পার্থক্যকে বলে ব্যালেন্স ফ্যাক্টর। এটি সাধারণত -১, ০, বা +১ হতে পারে।

রোটেশন অপারেশন:

• LL (Left-Left): বাম দিকে ভারী হলে ডান দিকে রোটেশন।
• RR (Right-Right): ডান দিকে ভারী হলে বাম দিকে রোটেশন।
• LR (Left-Right): বাম-ডান ভারী হলে বামে ঘুরে তারপর ডানে রোটেশন।
• RL (Right-Left): ডান-বাম ভারী হলে ডানে ঘুরে তারপর বামে রোটেশন।

অপারেশন:

• সন্নিবেশ (Insertion): মান যোগ করার পরে ব্যালেন্স ফ্যাক্টর পরীক্ষা করা হয় এবং প্রয়োজনে রোটেশন করে ট্রি ব্যালেন্স করা হয়।
• ডিলিশন (Deletion): নোড মুছে ফেলার পর ট্রির ভারসাম্য পরীক্ষা করা হয় এবং প্রয়োজন অনুযায়ী রোটেশন করা হয়।

সংক্ষেপে (Summary)

• বাইনারি ট্রি: প্রতিটি নোডের দুইটি সন্তান পর্যন্ত থাকতে পারে।
• BST: বাইনারি ট্রি যেখানে প্রতিটি নোডের বাম শিশু ছোট এবং ডান শিশু বড়।
• AVL ট্রি: একটি সেল্ফ-ব্যালেন্সিং BST, যেখানে নোডের বাম এবং ডান উপ-গাছের উচ্চতার পার্থক্য সর্বাধিক ১।

এই ট্রিগুলির প্রয়োগ বিভিন্ন ক্ষেত্রে ডেটা পরিচালনা এবং সংগঠনে ব্যবহার করা হয়। বিশেষত, AVL ট্রি তার দ্রুত গতি এবং ভারসাম্য বজায় রাখার ক্ষমতার কারণে দক্ষতা বৃদ্ধি করে।

ট্রাভার্সাল হলো একটি বাইনারি ট্রি বা গাছের সমস্ত নোডে একটি নির্দিষ্ট ক্রম অনুসারে ভ্রমণ করা। তিনটি প্রধান ট্রাভার্সাল পদ্ধতি রয়েছে: ইন-অর্ডার, প্রি-অর্ডার এবং পোস্ট-অর্ডার।

ইন-অর্ডার ট্রাভার্সাল (In-order Traversal)

ইন-অর্ডার ট্রাভার্সালে একটি নোডকে ভিজিট করার আগে তার বাম সাবট্রি (Left Subtree) ভিজিট করা হয় এবং তারপর ডান সাবট্রিতে (Right Subtree) যাওয়া হয়। এটি সাধারণত বাইনারি সার্চ ট্রিতে ব্যবহার করা হয়, কারণ এই পদ্ধতিতে ট্রি’র নোডগুলি সাজানো ক্রমে আসে।

ইন-অর্ডার পদ্ধতি:

1. বাম সাবট্রি ট্রাভার্স করুন।
2. রুট নোড ভিজিট করুন।
3. ডান সাবট্রি ট্রাভার্স করুন।

উদাহরণ: যদি একটি ট্রি এইরকম হয়:

     1
    / \
   2   3
  / \
 4   5

ইন-অর্ডার ট্রাভার্সালের আউটপুট হবে: ৪, ২, ৫, ১, ৩

প্রি-অর্ডার ট্রাভার্সাল (Pre-order Traversal)

প্রি-অর্ডার ট্রাভার্সালে প্রতিটি নোডের রুট আগে ভিজিট করা হয়, তারপর বাম সাবট্রি এবং সর্বশেষে ডান সাবট্রি। এই পদ্ধতিটি সাধারণত ট্রির গঠন পুনর্নির্মাণে বা কপি করতে ব্যবহৃত হয়।

প্রি-অর্ডার পদ্ধতি:

1. রুট নোড ভিজিট করুন।
2. বাম সাবট্রি ট্রাভার্স করুন।
3. ডান সাবট্রি ট্রাভার্স করুন।

উদাহরণ: উপরের ট্রি অনুসারে প্রি-অর্ডার ট্রাভার্সালের আউটপুট হবে: ১, ২, ৪, ৫, ৩

পোস্ট-অর্ডার ট্রাভার্সাল (Post-order Traversal)

পোস্ট-অর্ডার ট্রাভার্সালে প্রতিটি নোডের বাম এবং ডান সাবট্রি প্রথমে ভিজিট করা হয় এবং শেষে রুট নোডে পৌঁছানো হয়। এই পদ্ধতিটি ডিলিট অপারেশন এবং এক্সপ্রেশন ট্রির মূল্যায়নে ব্যবহার করা হয়।

পোস্ট-অর্ডার পদ্ধতি:

1. বাম সাবট্রি ট্রাভার্স করুন।
2. ডান সাবট্রি ট্রাভার্স করুন।
3. রুট নোড ভিজিট করুন।

উদাহরণ: উপরের ট্রি অনুসারে পোস্ট-অর্ডার ট্রাভার্সালের আউটপুট হবে: ৪, ৫, ২, ৩, ১

সংক্ষেপে (Summary)

• ইন-অর্ডার: বাম -> রুট -> ডান (৪, ২, ৫, ১, ৩)
• প্রি-অর্ডার: রুট -> বাম -> ডান (১, ২, ৪, ৫, ৩)
• পোস্ট-অর্ডার: বাম -> ডান -> রুট (৪, ৫, ২, ৩, ১)

স্প্যানিং ট্রি (Spanning Tree)

স্প্যানিং ট্রি হল একটি সংযুক্ত গ্রাফের এমন একটি সাব-গ্রাফ যা গ্রাফের সকল নোডকে সংযুক্ত করে কিন্তু কোন চক্র (Cycle) তৈরি করে না। এটি মূল গ্রাফের সব নোড অন্তর্ভুক্ত করে এবং শুধুমাত্র \( n - 1 \) টি এজ থাকে, যেখানে \( n \) হল নোডের সংখ্যা। স্প্যানিং ট্রিতে মূল গ্রাফের তুলনায় কম এজ থাকে এবং এটি এমনভাবে গঠিত হয় যে প্রতিটি নোড অন্য নোডের সাথে সংযুক্ত থাকে।

বৈশিষ্ট্যসমূহ

• প্রতিটি সংযুক্ত গ্রাফের জন্য একাধিক স্প্যানিং ট্রি থাকতে পারে।
• স্প্যানিং ট্রিতে চক্র থাকে না।
• যদি গ্রাফে \( n \) টি নোড থাকে, তবে স্প্যানিং ট্রিতে সর্বদা \( n - 1 \) টি এজ থাকবে।

মিনিমাম স্প্যানিং ট্রি (Minimum Spanning Tree)

মিনিমাম স্প্যানিং ট্রি (MST) হল একটি বিশেষ ধরনের স্প্যানিং ট্রি যেখানে স্প্যানিং ট্রির এজগুলির মোট ওজন সর্বনিম্ন হয়। ওজনযুক্ত গ্রাফে বিভিন্ন এজের ওজন থাকতে পারে, এবং মিনিমাম স্প্যানিং ট্রি সেই ট্রি যা নোডগুলোকে সংযুক্ত করতে সর্বনিম্ন ওজনের এজ ব্যবহার করে।

বৈশিষ্ট্যসমূহ

• মিনিমাম স্প্যানিং ট্রি শুধুমাত্র ওজনযুক্ত গ্রাফের জন্য প্রযোজ্য।
• এজের মোট ওজন সর্বনিম্ন।
• একটি গ্রাফের একাধিক মিনিমাম স্প্যানিং ট্রি থাকতে পারে যদি একাধিক এজের ওজন সমান হয়।

উদাহরণ

একটি শহরের রাস্তাগুলিকে এমনভাবে সংযুক্ত করতে হবে যাতে রাস্তাগুলির নির্মাণ খরচ সর্বনিম্ন হয়, সেখানে মিনিমাম স্প্যানিং ট্রি ব্যবহার করা হয়।

মিনিমাম স্প্যানিং ট্রি খোঁজার অ্যালগরিদম

প্রিমস অ্যালগরিদম (Prim's Algorithm): এই অ্যালগরিদমটি একটি নোড থেকে শুরু করে প্রতিবারে সবচেয়ে কম ওজনের এজ যোগ করে গ্রাফের সকল নোডকে সংযুক্ত করে।

ক্রাসকালস অ্যালগরিদম (Kruskal's Algorithm): এই অ্যালগরিদমটি গ্রাফের এজগুলিকে ওজনের ক্রমানুসারে সাজায় এবং চক্র তৈরি না করে সবচেয়ে কম ওজনের এজগুলিকে যুক্ত করে MST গঠন করে।

বাস্তব জীবনে প্রয়োগ (Applications)

• নেটওয়ার্ক ডিজাইন: কম্পিউটার নেটওয়ার্ক, টেলিকমিউনিকেশন নেটওয়ার্ক বা রাস্তার নেটওয়ার্কের ন্যূনতম খরচে সংযোগের জন্য MST ব্যবহার করা হয়।
• ক্লাস্টারিং অ্যালগরিদম: ডেটা ক্লাস্টারিংয়ে মিনিমাম স্প্যানিং ট্রি ব্যবহার করে ক্লাস্টার তৈরি করা যায়।

সারসংক্ষেপ (Summary)

স্প্যানিং ট্রি হল একটি সংযুক্ত গ্রাফের চক্রবিহীন সাব-গ্রাফ যা নোডগুলিকে সংযুক্ত করে। মিনিমাম স্প্যানিং ট্রি হল এমন একটি স্প্যানিং ট্রি যার মোট এজের ওজন সর্বনিম্ন। এটি নেটওয়ার্ক ডিজাইন, রাস্তা নির্মাণ এবং ক্লাস্টারিংয়ের মতো বিভিন্ন ক্ষেত্রে গুরুত্বপূর্ণ। প্রিমস এবং ক্রাসকালস অ্যালগরিদম MST খুঁজে বের করতে ব্যবহৃত হয়।